package SubjectHashTable;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class IsAnagram {

/**
 * 难度：简单
 * 
 * 242. 有效的字母异位词
 * 	给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * 
 * 示例 1:
 * 	输入: s = "anagram", t = "nagaram"
 * 	输出: true
 * 
 * 示例 2:
 * 	输入: s = "rat", t = "car"
 * 	输出: false
 * 
 * 说明:
 * 	你可以假设字符串只包含小写字母。
 * 
 * 进阶:
 * 	如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
 *
 * */	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsAnagram ia = new IsAnagram();
		System.out.println(ia.isAnagram3("rat", "car"));
	}
	//方法一：排序
	public boolean isAnagram1(String s, String t) {
		if(s.length()!=t.length()) {
			return false;
		}
		char[] sc=s.toCharArray();
		char[] tc=t.toCharArray();
		Arrays.sort(sc);
		Arrays.sort(tc);
		return Arrays.equals(sc, tc);
    }
	//方法二：哈希表1
	public boolean isAnagram2(String s, String t) {
		if(s.length()!=t.length()) {
			return false;
		}
		int[] table=new int[26];
		for(int i=0;i<s.length();i++) {
			table[s.charAt(i)-'a']++;
		}
		for(int i=0;i<t.length();i++) {
			table[t.charAt(i)-'a']--;
			if(table[t.charAt(i)-'a']<0) {
				return false;
			}
		}
		return true;
    }
	//方法三：哈希表2
	public boolean isAnagram3(String s, String t) {
		if(s.length()!=t.length()) {
			return false;
		}
		Map<Character,Integer> table = new HashMap<>();
		for(int i=0;i<s.length();i++) {
			char ch =s.charAt(i); 
			table.put(ch, table.getOrDefault(ch, 0)+1);
		}
		for(int i=0;i<t.length();i++) {
			char ch = t.charAt(i);
			table.put(ch, table.getOrDefault(ch, 0)-1);
			if(table.get(ch)<0) {
				return false;
			}
		}
		return true;
	}
}
